package com.mxw.leetcode.D2动态规划;

public class D01动态规划 {
    /**
     * 动态规划问题：一般形式求最值
     * 要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗：熟练掌握递归思维，只有列出正确的「状态转移方程」，才能正确地穷举。
     * <p>
     * 重叠子问题、最优子结构、状态转移方程就是动态规划三要素：
     * 明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
     * <p>
     * 框架：
     * # 自顶向下递归的动态规划：
     * 是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。
     * def dp(状态1, 状态2, ...):
     * for 选择 in 所有可能的选择:
     * # 此时的状态已经因为做了选择而改变
     * result = 求最值(result, dp(状态1, 状态2, ...))
     * return result
     * <p>
     * # 自底向上迭代的动态规划：
     * 已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。
     * # 初始化 base case
     * dp[0][0][...] = base case
     * # 进行状态转移
     * for 状态1 in 状态1的所有取值：
     * for 状态2 in 状态2的所有取值：
     * for ...
     * dp[状态1][状态2][...] = 求最值(选择1，选择2...)
     * <p>
     * <p>
     * 重叠子问题: 斐波那契数列
     * int fib(int N) {
     * if (N == 1 || N == 2) return 1;
     * return fib(N - 1) + fib(N - 2);
     * // f(20)->f(19)+f(18)
     * // f(19)->f(18)+f(17)->f(18)->f(17)+f(16);
     * // f(18)->f(17)+f(16)
     * f(18)就计算了两次
     * <p>
     * 我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；
     * 每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
     * 一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。
     * <p>
     * <p>
     * 状态转移方程：
     * f(n) 的函数参数会不断变化，所以你把参数 n 想做一个状态，这个状态 n 是由状态 n - 1 和状态 n - 2 转移（相加）而来，这就叫状态转移
     */
    int[] memo;

    int fib(int N) {
        // 备忘录全初始化为 0
        memo = new int[N + 1];
        // 进行带备忘录的递归
        return dpFun(N);
    }

    int dpFun(int i) {
        // base case
        if (i == 0 || i == 1) return i;
        // 已经计算过，不用再计算了
        if (memo[i] != 0) return memo[i];
        memo[i] = dpFun(i - 1) + dpFun(i - 2);
        return memo[i];
    }

    int fib2(int N) {
        if (N == 0) return 0;
        int[] dp = new int[N + 1];
        // base case
        dp[0] = 0;
        dp[1] = 1;
        // 状态转移
        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[N];
    }

}
